Algorithmes de recherche

En informatique, un tableau est une structure de données représentant une séquence finie d’éléments auxquels on peut accéder par leur position dans la séquence. On utilisera des listes Python pour représenter ces tableaux. On peut également remarquer qu’une chaîne de caractères est un tableau de caractères.

On s’intéresse dans ce paragraphe à divers algorithmes permettant de traiter des tableaux ou de retrouver de l’information dans ceux-ci.

Recherche d’un élément

On cherche à savoir si une valeur donnée fait bien partie des éléments d’un tableau. On parcourt tout simplement ce tableau et on renvoie True dès qu’on trouve cette valeur dans le tableau. Si la valeur n’a pas été trouvée à la fin du parcours, on renvoie False.

def appartient(valeur, tableau):
    for element in tableau:
        if element == valeur:
            return True
    return False

appartient('Alice', ['Alice', 'Bob', 'Charles-Antoine'])

True

appartient('Dédé', ['Alice', 'Bob', 'Charles-Antoine'])

False

Note

Le langage Python dispose de l’opérateur in pour déterminer si une valeur appartient à une liste.

'Alice' in ['Alice', 'Bob', 'Charles-Antoine']

True

'Dédé' in ['Alice', 'Bob', 'Charles-Antoine']

False

On peut modifier l’algorithme precédent afin qu’il renvoie l’indice du tableau où on a trouvé la valeur recherché et None si la valeur n’a pas été trouvée.

def indice(valeur, tableau):
    for i in range(len(tableau)):
        if tableau[i] == valeur:
            return i
    return None

indice(2, [5, 4, 1, 2, 3])

3

print(indice(6, [5, 4, 1, 2, 3]))

None

Note

La méthode index de la classe list permet de déterminer l’indice d’une valeur dans une liste.

[5, 4, 1, 2, 3].index(2)

3

[5, 4, 1, 2, 3].index(6)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Input In [10], in <cell line: 1>()
----> 1 [5, 4, 1, 2, 3].index(6)

ValueError: 6 is not in list

Recherche du maximum

def maximum(tableau):
    m = None
    for element in tableau:
        if m == None or m < element:
            m = element
    return m

maximum([4, 5, 8, 1, 3])

8

print(maximum([]))

None

def argmax(tableau):
    index = None
    for i in range(len(tableau)):
        if index == None or tableau[index] < tableau[i]:
            index = i
    return index

argmax([4, 5, 8, 1, 3])

2

print(argmax([]))

None

def second_maximum(tableau):
    m1 = None
    m2 = None
    for element in tableau:
        if m1 == None or m1 < element:
            m2 = m1
            m1 = element
        elif m2 == None or m2 < element:
            m2 = element
    return m2

second_maximum([4, 5, 8, 1, 3])

5

print(second_maximum([]))

None

print(second_maximum([2]))

None

Comptage des éléments d’un tableau

def comptage(tableau):
    d = {}
    for element in tableau:
        if element in d:
            d[element] += 1
        else:
            d[element] = 1
    return d

comptage(['Alice', 'Bob', 'Alice', 'Charles', 'Charles', 'Alice'])

{'Alice': 3, 'Bob': 1, 'Charles': 2}

Recherche d’un motif dans une chaîne

def recherche_motif(motif, chaine):
    n = len(chaine)
    m = len(motif)
    for ind in range(n-m+1):
        nb = 0
        while nb < m and chaine[ind+nb] == motif[nb]:
            nb +=1
        if nb == m:
            return True
    return False

recherche_motif("pipa", "pitapipapa")

True

Once Loop Reflect

recherche_motif("tapa", "patapipapa")

False

Once Loop Reflect

Recherche des deux valeurs les plus proches d’un tableau

def plus_proches_valeurs(tableau):
    valeurs = None
    for i in range(len(tableau)):
        for j in range(i+1, len(tableau)):
            if valeurs == None or abs(tableau[i] - tableau[j]) < abs(valeurs[0] - valeurs[1]):
                valeurs = tableau[i], tableau[j]
    return valeurs

plus_proches_valeurs([7, 4, 9, 13])

(7, 9)

print(plus_proches_valeurs([]))

None

print(plus_proches_valeurs([7]))

None

Tri à bulles

Le tri à bulles fait partie des algorithmes de tri classiques. Trier un tableau consiste à ordonner ses éléments du plus petit au plus grand. On suppose donc que les éléments du tableau sont à valeurs dans un ensemble muni d’une relation d’ordre total.

Le tri à bulles consiste à déplacer les éléments du plus grand au plus petit vers la fin du tableau comme des bulles d’air dans un liquide. Plus précisément :

• on parcourt le tableau en comparant les couples d’éléments consécutifs ;

• si deux éléments consécutifs ne sont pas dans le bon ordre, on les échange ;

• à la fin de ce premiers parcours du tableau, on peut garantir que le plus grand élément du tableau est en dernière position ;

• on répète alors ce qui précède sur le tableau privé de son dernier élément et ainsi de suite jusqu’à tri complet du tableau.

Once Loop Reflect

def tri_bulles(tableau):
    for i in reversed(range(len(tableau))):
        for j in range(i):
            if tableau[j+1] < tableau[j]:
                tableau[j], tableau[j+1] = tableau[j+1], tableau[j]

t = [4, 2, 5, 3, 8, 7, 6, 1]
tri_bulles(t)
t

[1, 2, 3, 4, 5, 6, 7, 8]

t = []
tri_bulles(t)
t

[]

t = [4]
tri_bulles(t)
t

[4]